In certain circumstances, it is useful to translate compiled machine code from a first state corresponding to a first instruction set to a second state corresponding to a second instruction set. As is known, such translating is preferable to the alternative: locating the source code from which the machine code in the first code state was derived; and writing and debugging a compiler to compile such located source code directly into the machine code in the second code state.
As is also known, such translating from the first code state to the second code state is performed by way of an appropriate re-compiler or translator on an appropriate processor with attached memory. In such translating from the first code state to the second code state, a control flow graph and an intermediate representation of the sequences of instructions is often helpful in the code optimization process and translating it from the first state to the second optimized state.
A directed graph provides a useful intermediate representation of sequences of instructions for a stack based computer. The representation is somewhat complicated by the fact that some instructions leave multiple results on the stack, which may then later be consumed by different successor instructions. The location on the expression stack and relationships between these results and the instructions that generated them are indicated by special graph nodes called “aliases.”
When considering certain possible code rearrangements (i.e., optimizations), it is crucial to know that certain sub-graphs of the whole are effectively independent of the rest, that is, self-contained, allowing for reordering without altering the integrity of the whole. With respect to aliases, this means that any aliases generated by nodes within the sub-graph must themselves be contained in it, and conversely, that any aliases in the sub-graph must have been generated by nodes also within it.
In this regard, there is a need for an efficient method for analyzing a graph that is an intermediate representation of sequences of instructions for a stack based computer and identifying its self-contained sub-graphs.